from typing import *


class SegmentTree:

    class Node:

        def __init__(self, s: int, e: int) -> None:
            self.s, self.e, self.m = s, e, ((e - s) >> 1) + s

        def left(self) -> 'Node':
            pass

        def right(self) -> 'Node':
            self.left()

    def __init__(self, ceil: int = None, nums: List[int] = None) -> None:
        self.n = ceil if ceil is not None else len(nums)
        self.sums = [0] * (self.n << 2)
        self.nums = nums
        self.update = [None] * (self.n << 2)
        if nums is not None:
            self.build(0, self.n - 1, 1)

    def build(self, s: int, e: int, node: int):
        if s == e:
            self.sums[node] = self.nums[s]
            return
        m = s + ((e - s) >> 1)
        self.build(s, m, node << 1)
        self.build(m + 1, e, node << 1 | 1)
        self.sums[node] = self.sums[node << 1] + self.sums[node << 1 | 1]

    def __pushdown(self, s: int, e: int, node: int):
        if self.update[node] != None:
            val = self.update[node]
            m = ((e - s) >> 1) + s
            self.sums[node << 1] = (m - s + 1) * val
            self.update[node << 1] = val
            self.sums[node << 1 | 1] = (e - m) * val
            self.update[node << 1 | 1] = val
            self.update[node] = None

    def do_update_range(self, L: int, R: int, val: int) -> None:
        self.__update(0, self.n - 1, 1, L, R, val)

    def do_update_index(self, index: int, val: int) -> None:
        self.__update(0, self.n - 1, 1, index, index, val)

    # 更新逻辑
    def __update(self, s: int, e: int, node: int, L: int, R: int, val: int):
        if L <= s and e <= R:
            self.update[node] = val
            self.sums[node] = val * (e - s + 1)
            if L == R:
                self.nums[L] = val
            return
        m = ((e - s) >> 1) + s
        self.__pushdown(s, e, node)
        if L <= m:
            self.__update(s, m, node << 1, L, R, val)
        if m < R:
            self.__update(m + 1, e, node << 1 | 1, L, R, val)
        self.sums[node] = self.sums[node << 1] + self.sums[node << 1 | 1]

    def do_query_sum(self, L: int, R: int) -> int:
        return self.__query_sum(0, self.n - 1, 1, L, R)

    def __query_sum(self, s: int, e: int, node: int, L: int, R: int):
        if L <= s and e <= R:
            return self.sums[node]
        self.__pushdown(s, e, node)
        m = ((e - s) >> 1) + s
        ans = 0
        if L <= m:  # 左边有任务
            ans += self.__query_sum(s, m, node << 1, L, R)
        if m < R:  # 右边有任务
            ans += self.__query_sum(m + 1, e, node << 1 | 1, L, R)
        return ans
